#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include "../include/mm.h"
using std::cout;
using std::cerr;
using std::endl;

static const uint32_t WORD_SIZE = sizeof(uint32_t);
static const uint32_t NODE_SIZE = sizeof(NodeType);
typedef unsigned char byte;

MemoryManager::MemoryManager()
  : unusedNodeList(0), usedNodeList(0),
    totalSize(MemoryManager::DEFAULT_MEM_SIZE),
    usableSize(totalSize - MemoryManager::DEFAULT_MEM_SIZE / 100 / NODE_SIZE),
    numListNodes(MemoryManager::DEFAULT_MEM_SIZE / 100 / NODE_SIZE),
    totalRequestCount(0), totalRequestSize(0),
    totalGrantedRequestCount(0),
    totalGrantedRequestSize(0),
    totalFailedRequestCount(0),
    totalFailedRequestSize(0),
    bytesUsed(0),
    memory(0)
{
  this->memory = malloc(this->totalSize);
  if(this->memory == 0){
    perror("MemoryManager::init");
    exit(EXIT_FAILURE);
  }

  // set all bytes of memory allocated to 0
  for (uint32_t i = 0; i < this->totalSize; ++i){
    static_cast<byte*>(this->memory)[i] = 0;
  }

  this->init();
}

MemoryManager::MemoryManager(const uint32_t memoryNumBytes,
			     const uint32_t freeListNumBytes)
  : unusedNodeList(0), usedNodeList(0),
    totalSize(memoryNumBytes),
    usableSize(memoryNumBytes - freeListNumBytes),
    numListNodes(freeListNumBytes / NODE_SIZE),
    totalRequestCount(0), totalRequestSize(0),
    totalGrantedRequestCount(0),
    totalGrantedRequestSize(0),
    totalFailedRequestCount(0),
    totalFailedRequestSize(0),
    bytesUsed(0),
    memory(0)
{
  if (memoryNumBytes < freeListNumBytes) {
    cerr << "error: Memory size(" << memoryNumBytes
	 << ") must be more than list node memory(" << freeListNumBytes
	 << ").\n";
    exit(EXIT_FAILURE);
  }

  this->memory = malloc(memoryNumBytes);
  if(this->memory == 0){
    perror("MemoryManager::init");
    exit(EXIT_FAILURE);
  }

  if (this->numListNodes < 3) {
    cerr << "error: Please allocate an additional "
	 << (3 - this->numListNodes) * NODE_SIZE
	 << "bytes for list nodes.\n";
    exit(EXIT_FAILURE);
  }

  // set all bytes of memory allocated to 0
  for (uint32_t i = 0; i < this->totalSize; ++i){
    static_cast<byte*>(this->memory)[i] = 0;
  }

  this->init();
}


void
MemoryManager::init()
{
  printf("%d bytes allocated, %d bytes usable, %d bytes for %d list nodes.\n\n",
	 this->totalSize,
	 this->usableSize,
	 this->totalSize - this->usableSize,
	 this->numListNodes);

  // here is your code to initialize the available linked list
  // initially, only one node is in the list
  this->usedNodeList = static_cast< NodeType* >(this->memory);
  NodeType *node = this->usedNodeList;
  node->data = this->usedNodeList + this->numListNodes;
  node->size = 0;
  node->isFree = true;
  // the head IS the tail
  node->prev = node;
  // null is the end of the line
  node->next = NULL;

  // here is your code to initialize the unused list nodes
  // these nodes use the memory pointed to by real_memory
  // You are not allowed to use any other memory for maintain
  // the list nodes: there should be no other malloc or new in your code
  unusedNodeList = node + 1;
  // for convenience we link the end of the used list to the prev pointer of the
  // head of the unused list (note that this is not reciprocated)
  unusedNodeList->prev = node;
  for (uint32_t i = 0; i < numListNodes - 1; ++i) {
    NodeType *unused = unusedNodeList + i;
    if (i > 0)
      unused->prev = &unusedNodeList[i - 1];
    if (i < numListNodes - 2)
      unused->next = &unusedNodeList[i + 1];
    if (i < numListNodes - 1)
      unused->isFree = true;
  }

  // set the free list bytes as used
  bytesUsed += (numListNodes * NODE_SIZE);
}

void
MemoryManager::printMemoryStatus(const uint32_t level)
{
  uint32_t freeMemory, unusedListNodeCnt, allocatedMemory, usedListNodeCnt;
  freeMemory = unusedListNodeCnt = allocatedMemory = usedListNodeCnt = 0;

  for (NodeType *p = this->usedNodeList; p != NULL; p = p->next){
    if (p->isFree)
      freeMemory += p->size;
    else
      allocatedMemory += p->size;
    ++usedListNodeCnt;
  }
  // since I don't keep the whole unused block in the used List free can
  // more easily be found by total - allocated
  freeMemory = usableSize - allocatedMemory;

  cout << "Total usable memory: " << this->usableSize << " bytes\n"
       << "Total free memory:" << freeMemory << " bytes\n"
       << "Total allocated memory:" << allocatedMemory << " bytes\n"

       << "\nTotal available list nodes: " << this->numListNodes << "\n"
       << "Total used list nodes: " << usedListNodeCnt << "\n";

  for (NodeType *p = this->unusedNodeList; p != NULL; p = p->next){
    ++unusedListNodeCnt;
  }

  cout << "Total unused list nodes: " << unusedListNodeCnt << "\n";

  if (level >= 10 ) {
    cout << "\nFree blocks: \n";
    for (NodeType *p = this->usedNodeList; p != NULL; p = p->next){
      if (p->isFree){
	const uint32_t address =
	  static_cast<byte*>(p->data) - static_cast<byte*>(this->memory);
	cout << "  free block: addr=" << address;
	// again I don't keep a huge unallocated block in the used list
	if (p->size > 0)
	  cout <<  ", size=" << p->size << "\n";
	else
	  cout << ", size=" << freeMemory << "\n";
      }
    }

    cout << "\nUsed blocks:\n";
    for (NodeType *p = this->usedNodeList; p != NULL; p = p->next){
      if (p->isFree == false) {
	const size_t address =
	  static_cast<byte*>(p->data) - static_cast<byte*>(this->memory);
	cout << "  used block: addr=" << address
	     << ", size=" << p->size << "\n";
      }
    }
  }

  if (level >= 100) {
    cout << "\nMemory content:\n";
    for (unsigned short i = 0; i < this->usableSize; ++i) {
      const byte *const address =
	(static_cast<byte*>(this->memory) +
	 this->totalSize - this->usableSize + i);
      if (i % 16 == 0) {
	printf("\n%X: ", i);
      }
      printf("%X ", address);
    }
    cout << "\n";
  }
}


void
MemoryManager::printUseList() {

  printf("Use list: \n");
  for (NodeType *p = this->usedNodeList; p != NULL; p = p->next){
    const uint32_t address =
      static_cast<byte*>(p->data) - static_cast<byte*>(this->memory);
    cout << "(" << p->size << "," << p->isFree << "," << address << ")\n";
  }
}

// get a NodeType node to use
NodeType *
MemoryManager::getUnusedBlock()
{
  NodeType *unused = 0;
  // moves a node from the head of the unused list to the tail of the used list
  if (unusedNodeList != NULL) {
    unused = unusedNodeList;
    // Reset the next link in line to be the unusedNodeList head. If this link is
    // NULL it means the end of the list, and the list itself should become NULL.
    unusedNodeList = unusedNodeList->next;
    // Disconnect the link pointers from the old head to the rest of the unused.
    // NOTE: there may be no next pointer if this is the last node, so we check
    if (unused->next != NULL)
      unused->next->prev = NULL;
    unused->next = NULL;
  }
  return unused;
}

void
MemoryManager::releaseUnusedBlock(NodeType *p)
{
  // This basically takes a NodeType whose data block was coalesced.
  if (p != 0) {
    p->prev->next = p->next;
    // if we are releasing the very last block, it has no next
    if (p->next != NULL)
      p->next->prev = p->prev;
    p->isFree = true;
    p->size = 0;

    // if there is no waiting node, make node the waiting node
    if (usedNodeList->prev->size > 0) {
      usedNodeList->prev->next = p;
      p->prev = usedNodeList->prev;
      // set our data to the position after the last node
      p->data = static_cast<byte*>(usedNodeList->prev->data) + usedNodeList->prev->size;
      p->next = NULL;
      usedNodeList->prev = p;
    }
    // The node is no longer needed and there is already a waiting node,
    // so node p can be returned to the free list.
    else {
      p->prev = NULL;

      // this only works if unusedNodeList isn't null
      if (unusedNodeList != NULL) {
        unusedNodeList->prev = p;
        p->next = unusedNodeList;
      }
      else {
        p->next = NULL;
      }
      p->data = 0;
      unusedNodeList = p;
    }
  }
}


void
MemoryManager::setAllocMode(const AllocMode mode) {
  this->mode = mode;
}


void *
MemoryManager::mymalloc(const uint32_t requestSize)
{
  void * mem = 0;

  ++totalRequestCount;
  totalRequestSize += requestSize;

  switch(this->mode){
  case FIRST_FIT:
    mem = allocFirstFit(requestSize);
    break;
  case BEST_FIT:
    mem = allocBestFit(requestSize);
    break;
  case WORST_FIT:
    mem = allocWorstFit(requestSize);
    break;
  case CUSTOM:
    /* will you try something else? */
  default:
    mem = allocFirstFit(requestSize);
    break;
  }

  // get statistics based on mem result
  if (mem == 0) {
    // request failed!
    ++totalFailedRequestCount;
    totalFailedRequestSize += requestSize;
  }
  else {
    ++totalGrantedRequestCount;
    totalGrantedRequestSize += requestSize;
    bytesUsed += requestSize;
  }

  return mem;
}

void *
MemoryManager::allocFirstFit(const uint32_t requestSize)
{
  void *mem = 0;
  NodeType *lastValidNode = NULL;
  bool openNodeExists;

  // Per Alejandro: if we cannot allocate an EXACT size we must fail. For this to
  // happen we must have an open node to split to or the found block MUST be the
  // size requested. Use the openNodeExists to identify if there is a free block.
  openNodeExists = false;
  if (usedNodeList->prev != NULL && usedNodeList->prev->size == 0)
    openNodeExists = true;

  // First loop over the "used" list (i.e. allocated) to see if there is a free
  // block that fits the request.
  for (NodeType *p = this->usedNodeList; p != NULL; p = p->next){
    lastValidNode = p;

    if (p->isFree && ((openNodeExists && p->size > requestSize) || p->size == requestSize)) {
      mem = p->data;
      p->isFree = false;
      // If the free, allocated memory was more than we need, split it.
      // If this doesn't succeed (for instance if there are no free nodes), we
      // return and p retains the original larger size.
      if (p->size > requestSize)
        splitMemory(p, requestSize);

      // stop looking for satisfying blocks since we found one
      break;
    }
  }

  // If no allocated free blocks found, chip off a new piece of unallocated memory.
  // The ending address for p should be the next node to get memory. We pass p
  // so that we know which is the final block.
  if (mem == 0)
    mem = allocNewMemory(lastValidNode, requestSize);

  return mem;
}


void *
MemoryManager::allocBestFit(const uint32_t requestSize)
{
  void *mem = 0;
  NodeType *lastValidNode = NULL, *bestFit = NULL;
  bool openNodeExists;

  // Per Alejandro: if we cannot allocate an EXACT size we must fail. For this to
  // happen we must have an open node to split to or the found block MUST be the
  // size requested. Use the hasOpenNode to identify if there is a free block.
  openNodeExists = false;
  if (usedNodeList->prev != NULL && usedNodeList->prev->size == 0)
    openNodeExists = true;

  // First loop over the "used" list (i.e. allocated) to find all satisfying blocks
  // but only keeping track of the smallest (i.e. bestFit)
  for (NodeType *p = this->usedNodeList; p != NULL; p = p->next){
    lastValidNode = p;
    if (p->isFree && ((openNodeExists && p->size > requestSize) || p->size == requestSize) && (bestFit == 0 || p->size < bestFit->size)) {
      bestFit = p;
      // hold off finishing moves until we've seen everything
    }
  }

  // If no allocated free blocks found, chip off a new piece of unallocated memory.
  // The ending address for p should be the next node to get memory. We pass p
  // so that we know which is the final block.
  if (bestFit == 0)
    mem = allocNewMemory(lastValidNode, requestSize);
  else {
    mem = bestFit->data;
    bestFit->isFree = false;
    // Even if this IS the best fit we've found, we size it exactly if we can.
    if (bestFit->size > requestSize)
      splitMemory(bestFit, requestSize);
  }
  return mem;
}


void *
MemoryManager::allocWorstFit(const uint32_t requestSize)
{
  void *mem = 0;
  NodeType *lastValidNode = NULL, *worstFit = NULL;
  bool openNodeExists;

  // Per Alejandro: if we cannot allocate an EXACT size we must fail. For this to
  // happen we must have an open node to split to or the found block MUST be the
  // size requested. Use the hasOpenNode to identify if there is a free block.
  openNodeExists = false;
  if (usedNodeList->prev != NULL && usedNodeList->prev->size == 0)
    openNodeExists = true;

  // First loop over the "used" list (i.e. allocated) to find all satisfying blocks
  // but only keeping track of the largest (i.e. worstFit)
  for (NodeType *p = this->usedNodeList; p != NULL; p = p->next){
    lastValidNode = p;
    if (p->isFree && ((openNodeExists && p->size > requestSize) || p->size == requestSize) && (worstFit == 0 || p->size > worstFit->size)) {
      worstFit = p;
      // hold off finishing moves until we've seen everything
    }
  }

  // If no allocated free blocks found, chip off a new piece of unallocated memory.
  // The ending address for p should be the next node to get memory. We pass p
  // so that we know which is the final block.
  if (worstFit == 0)
    mem = allocNewMemory(lastValidNode, requestSize);
  else {
    mem = worstFit->data;
    worstFit->isFree = false;
    // Even if this IS the worst fit we've found, we size it exactly if we can.
    if (worstFit->size > requestSize)
      splitMemory(worstFit, requestSize);
  }
  return mem;
}


void *
MemoryManager::allocNewMemory(NodeType *p, const uint32_t requestSize)
{
  void *mem = 0;
  byte *finalAddress, *dataBytePtr;
  NodeType *n;
  uint32_t alignedSize = requestSize;

  // Use mod math to make sure the size used remains aligned. Note that 0 back
  // from mod means no remainder and this adjustment gets skipped.
  if (alignedSize % 4) alignedSize += (4 - (alignedSize % 4));

  // This block should already be part of the usedNodeList. It's size should be
  // 0 meaning that it is at the next available memory space but hasn't been
  // assigned any memory yet. Also, it's memory should be a valid address.
  finalAddress = static_cast<byte *>(memory) + totalSize;
  if (p->isFree && p->data > 0 && p->size == 0) {
    // create a byte pointer to the data location
    dataBytePtr = static_cast<byte *>(p->data);
    // make sure that we have enough memory to satisfy the request
    if (static_cast<uint32_t>(finalAddress - dataBytePtr) >= alignedSize) {
      p->size = alignedSize;
      p->isFree = false;
      mem = p->data;
      // Put a new used but unallocated block on the end of the list.
      n = getUnusedBlock();
      // make sure we got a valid node
      if (n != NULL) {
        p->next = n;
        n->prev = p;
        // Point the usedNodeList head's previous to the new node (the tail).
        if (usedNodeList != 0)
          usedNodeList->prev = n;
        // point n's address to the byte after p's data
        n->data = dataBytePtr += p->size;
        // double check that we haven't gone beyond the end of our memory
        if (dataBytePtr > finalAddress)
          n->data = NULL;
      }
    }
  }
  return mem;
}


/*
 * splitMemory takes a usedNode that is passed in and a size to shrink the used
 * node to. The left over memory is allocated to the last used node (the one with
 * 0 size) which is linked into the list right after the node that it inherited
 * memory from. This will allow us to coalesce memory if two chunks are freed next
 * to each other.
 */
void
MemoryManager::splitMemory(NodeType *p, const uint32_t requestSize)
{
  NodeType *n = 0;

  // This could be a place to attempt an optimization. If we are running low on nodes,
  // check to see if the node to resize would be better used on some free memory.
  // But probably need to track a free nodes statistic to avoid looping over list to count.

  // Make sure it makes sense to split the passed node. If not, go back.
  if (p->size <= requestSize)
    return;
  // If we still have an unused head, get a new node for the split. We avoid using
  // the "waiting" block if possible because it means less switching around.
  // NOTE: usedNodeList->prev still points to the next node to allocate
  // which also points to (->data) the next piece of memory to use.
  if (unusedNodeList != 0)
    n = getUnusedBlock();
  // Otherwise find n by going to the tail used node position (prev of head).
  else
    n = usedNodeList->prev;

  // make sure we have a node we can use, otherwise leave well-enough alone
  if (n->isFree && n->data == 0 && n->size == 0) {
    n->size = p->size - requestSize;
    p->size = requestSize;
    n->data = static_cast<byte*>(p->data) + p->size;
    // link n into the list right after p
    n->next = p->next;
    n->prev = p;
    p->next = n;
  }
}


/*
 * coalesceMemory tries to combine adjacent free, allocated memory blocks.
 */
void
MemoryManager::coalesceMemory(NodeType *p)
{
  NodeType *temp = 0;
  if (p != NULL) {
    // the memory allocations should stay in order but we still check to make sure
    // they really are adjacent data allocations
    if (p->prev != NULL && p->prev->isFree && p->prev->size != 0 && p->data == static_cast<byte*>(p->prev->data) + p->prev->size){
      p->prev->size += p->size;
      temp = p->prev;
      releaseUnusedBlock(p);
      // reset p so that we can perform another coalesce below if applicable
      p = temp;
    }
    // here we try to coalesce with the next block if it is not the end block
    if (p->next != NULL && p->next->isFree && p->next->size != 0 && p->next->data == static_cast<byte*>(p->data) + p->size) {
      p->size += p->next->size;
      releaseUnusedBlock(p->next);
    }
    // Here we check to see if the next block is the end block. If it is, we reset size to 0 since that is how we treat the large end piece
    if (p->next != NULL && p->next->isFree && p->next->size == 0 && p->next->data == static_cast<byte*>(p->data) + p->size) {
      p->size = 0;
      releaseUnusedBlock(p->next);
    }
    cerr<<"end \n";
  }
}


void
MemoryManager::myfree(void *ptr)
{
  NodeType *p = 0;

  // find the node
  for (p = this->usedNodeList; p != NULL; p = p->next){
    if (p->data == ptr) {
      p->isFree = true;
      break;
    }
  }

  /*
  if (p > 0)
    // try to coalesce memory around p
    coalesceMemory(p);
  */
}

MemoryManager::~MemoryManager()
{
  free(this->memory);

  printf( "\nMemory system performance statistics: \n");
  printf("\nNumber of requests: %u, total requested size: %u bytes\n",
         this->totalRequestCount,
	 this->totalRequestSize);
  printf("Granted requests: %u, granted size: %u\n",
	 this->totalGrantedRequestCount,
         this->totalGrantedRequestSize);
  printf("Failed requests: %u, failed size: %u\n",
	 this->totalFailedRequestCount,
         this->totalFailedRequestSize);
}
